package features.advance.leetcode.math.medium;

/**
 *  剑指 Offer 44. 数字序列中某一位的数字
 *
 *  难度：中等
 *
 * 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，
 * 第13位是1，第19位是4，等等。
 *
 * 请写一个函数，求任意第n位对应的数字。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：3
 * 示例 2：
 *
 * 输入：n = 11
 * 输出：0
 *
 *
 * 限制：
 *
 * 0 <= n < 2^31
 * 注意：本题与主站 400 题相同：https://leetcode-cn.com/problems/nth-digit/
 *
 * @author LIN
 * @date 2021-06-02
 */
public class Offer44 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
            @Override
            public int findNthDigit(int n) {
                int digit = 1;
                long start = 1;
                long count = 9;
                while (n > count) { // 1.
                    n -= count;
                    digit += 1;
                    start *= 10;
                    count = digit * start * 9;
                }
                long num = start + (n - 1) / digit; // 2.
                return Long.toString(num).charAt((n - 1) % digit) - '0';
            }
        };
        int num = 1000000000;
        int nthDigit = solution.findNthDigit(num);
        System.out.println(nthDigit);
    }
    /**
    digit位数
    start数字的起始数字
    count数位数量
    0123456789                                      9*1
    1011121314151171819
    20212223242526272829
    ...
    90919293949596979899                            20*9
    100101102103104105106107108109
    110111112113114115116117118119
    ...
    990991992993994995996997998999                  30*9    digit * 10 * 9
    1001100210031004100510061007100810091010                count = 9 * start * digit


     10+20+30+40+50...+10*n
     (1+n) * n/2 * 10^n
     数字的位数：digiit
     digit位数第一个数字：start
     先算数字是几位，求出digit，再求出数字是多少，再算是该数字的第几个数
     */
    static class Solution{
        public int findNthDigit(int n){
            int digit = 1;
            long start = 1,count = 9;

            while(n > count){
                n -=count;
                digit++;
                start*=10L;
                count = digit * start * 9;
            }
            return ((start+(n-1)/digit)+"").charAt((n-1)%digit)-'0';
        }
    }
}
